package day03

// day03
//
// 496. 下一个更大元素 I
//
// https://leetcode.cn/problems/next-greater-element-i/
//
// ```go
func nextGreaterElement(nums1 []int, nums2 []int) []int {
	mp := map[int]int{}
	for i := range nums1 {
		mp[nums1[i]] = i
	}
	stack := make([]int, 0)
	ans := make([]int, len(nums1))
	for i := range ans {
		ans[i] = -1
	}
	for i := range nums2 {
		val := nums2[i]
		if len(stack) > 0 {
			for len(stack) > 0 {
				topIdx := stack[len(stack)-1]
				if val > nums2[topIdx] {
					if idx, ok := mp[nums2[topIdx]]; ok {
						ans[idx] = val
					}
					stack = stack[:len(stack)-1]
				} else {
					break
				}

			}
		}
		stack = append(stack, i)
	}
	return ans
}

//```

// 503. 下一个更大元素 II
//
// https://leetcode.cn/problems/next-greater-element-ii/
//
// ```go
func nextGreaterElements(nums []int) []int {
	nums = append(nums, nums...)
	stack := make([]int, 0)
	ans := make([]int, len(nums)+1)
	for i := range ans {
		ans[i] = -1
	}
	for i := range nums {
		val := nums[i]
		if len(stack) > 0 {
			for len(stack) > 0 {
				topIdx := stack[len(stack)-1]
				if val > nums[topIdx] {
					ans[topIdx] = val
					stack = stack[:len(stack)-1]
				} else {
					break
				}
			}
		}
		stack = append(stack, i)
	}
	return ans[:len(ans)/2]
}

//```
